package com.roamer.javase.demo.algorithm;

import java.util.*;

/**
 * 乐扣算法题
 *
 * @author roamer
 * @version v1.0
 * @date 2019/9/23 09:52
 */
public class Solution {

    /**
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     * 示例:
     * 给定 nums = [2, 7, 11, 15], target = 9
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     * <p>
     * 链接：https://leetcode-cn.com/problems/two-sum
     *
     * @param nums   数组
     * @param target 目标值
     * @return {@code int[]}
     */
    static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[i] + nums[j]) == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[2];
    }

    static int[] twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            // 放入补码
            map.put(target - nums[i], i);
        }
        return new int[2];
    }

    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，
     * 并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 示例：
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * <p>
     * 链接：https://leetcode-cn.com/problems/add-two-numbers
     *
     * @param l1 数字1
     * @param l2 数字2
     * @return {@code ListNode}
     */
    static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 初始余数为0
        int quotient = 0;
        ListNode header = new ListNode(0), node = header;
        while (null != l1 || null != l2) {
            if (l1 != null) {
                quotient += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                quotient += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(quotient % 10);
            // 计算下一轮余数
            quotient = quotient / 10;
            node = node.next;
        }
        if (quotient > 0) {
            node.next = new ListNode(quotient);
        }
        return header.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        ListNode addNext(int next) {
            this.next = new ListNode(next);
            return this.next;
        }
    }

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 示例 1:
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
     *
     * @param s 字符串
     * @return {@code int} 最大不重复子字符串长度
     */
    static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        // 暴力循环
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s, i, j)) {
                    ans = Math.max(ans, j - i);
                }
            }
        }
        return ans;
    }

    private static boolean allUnique(String s, int start, int end) {
        Set<Character> map = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (map.contains(ch)) {
                return false;
            }
            map.add(ch);
        }
        return true;
    }

    static int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        int i = 0, j = 0, ans = 0;
        // 基于滑动窗口
        Set<Character> map = new HashSet<>(n);
        while (i < n && j < n) {
            if (!map.contains(s.charAt(j))) {
                // 滑动窗口右端移动
                map.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                // 滑动窗口左端移动
                map.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    static int lengthOfLongestSubstring2(String s) {
        int n = s.length(), ans = 0;
        // 优化滑动窗口
        Map<Character, Integer> map = new HashMap<>(n);
        // j++为滑动窗口右端移动
        for (int i = 0, j = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                // 滑动窗口左端移动
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(j - i + 1, ans);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }


    /**
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * 示例 1：
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     * 输入: "cbbd"
     * 输出: "bb"
     * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
     *
     * @param s 字符串
     * @return {@code String} 最大回文子字符串
     */
    public String longestPalindrome(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < n; j++) {
            if (map.containsKey(s.charAt(map.get(j)))) {
                i = Math.max(map.get(j), i);
            }

            map.put(s.charAt(j), j);
        }
        return null;
    }

    /**
     * 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
     * 示例 1:
     * 输入: 123
     * 输出: 321
     * 示例 2:
     * 输入: -123
     * 输出: -321
     * 示例 3:
     * 输入: 120
     * 输出: 21
     * 注意:
     * 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，
     * 如果反转后整数溢出那么就返回 0。
     * 链接：https://leetcode-cn.com/problems/reverse-integer
     *
     * @param x
     * @return
     */
    public static int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x = x / 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }
            rev = rev * 10 + pop;
        }
        return rev;
    }


}

class BTree<E> {
    private Node<E> root = new Node<>(null);
    private int size;

    public List<E> getData() {
        return beforeQuery();
    }

    private List<E> beforeQuery() {
        if (size < 1) {
            return Collections.emptyList();
        }
        List<E> values = new ArrayList<>(size);
        return beforeQuery(this.root, values);
    }

    private List<E> beforeQuery(Node<E> node, List<E> values) {
        if (Objects.nonNull(node.data)) {
            values.add(node.data);
            if (Objects.nonNull(node.left)) {
                beforeQuery(node.left, values);
            }
            if (Objects.nonNull(node.right)) {
                beforeQuery(node.right, values);
            }
        }
        return values;
    }

    static class Node<T> {
        private T data;
        private Node<T> left;
        private Node<T> right;

        public Node(T data) {
            this.data = data;
        }

        private Node(T data, Node<T> left, Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getLeft() {
            return left;
        }

        public void setLeft(Node<T> left) {
            this.left = left;
        }

        public Node<T> getRight() {
            return right;
        }

        public void setRight(Node<T> right) {
            this.right = right;
        }
    }
}
